package com.practice.sequence;

public class LongestIncreasingSub {
	public int[] findLongestIncreasingSubsequence(int[] a) {
		int n = a.length;
		int[] M = new int[n];
		int[] P = new int[n];
		int L = 0;
		
		for (int i=0; i<n; i++) {
			int j = findJ(a, M, i, 0, L);
			P[i] = M[j];
			if (j==L || a[i] < a[M[j+1]]) {
				M[j+1] = i;
				if (j+1 > L) L = j+1;
			}
		}

		int[] l = new int[L];
		int k = M[L];
		for (int i=0; i<L; i++) {
			l[L-i-1] = a[k];
			k = P[k];
		}
		
		return l;
	}
	
	private int findJ(int[] a, int[] M, int i, int lower, int upper) {
		int j = (lower+upper)/2;
		if (lower == upper) return a[M[j]]<a[i]? j : 0;
		if (lower == upper-1) return a[M[upper]]<a[i]? upper : lower;
		return a[M[j]] < a[i]? findJ(a, M, i, j, upper) : findJ(a, M, i, lower, j);
	}
	
	/*
	private int findJ(int[] a, int[] M, int i, int L) {
		int j = 0;
		for (int k=1; k<=L; k++) {
			if (a[M[k]] < a[i]) j = k;
		}
		return j;
	}
	*/
}
